Lossy encoding tries to represent data, e.g. audio or video data, with as few bits as possible while at the same time trying to allow the data to be reconstructed from the lossy encoded representation as good as possible.
To achieve this goal, commonly a rate-distortion cost function is defined. Minimizing this function then allows for a lossy compression scheme which delivers the best trade-off between encoding costs in terms of bitrate and information loss in terms of distortion of reconstructed data with respect to original data.
Reconstructing the data may comprise post-processing. That is, first a preliminary reconstruction of the data is generated using the information contained in the encoded data. Then, a post-processing method is applied for regaining that part of information which was removed from the original data by lossy compression.
An example thereof is the removal of film grain noise from image data in course of lossy compression and subsequent addition of simulated film grain noise to a preliminary reconstruction obtained from the lossy encoded image data.
Another exemplary source of distortion is quantization. For compressing video or audio data, the data is commonly predicted using already encoded data. The residual remaining form prediction is the transformed from spatial and/or temporal domain to frequency domain using, for instance, discrete cosine transformation or wavelet transformation. The resulting coefficients then are quantized. Finally, the quantized coefficients are encoded using, e.g., Huffman coding or arithmetic encoding.
Quantization can be non-linear such that the coefficients are thinned out or sparsified, i.e. only a sub-set of the frequency information is maintained. This is similar or identical to linear quantization combined with modification. E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. on Information Theory, vol. 52, pp. 489-509, February 2006, proved theoretically that, anyway, image can be exactly reconstructed from such sub-set using appropriate post-processing.
Y. Zhang, S. Mei, Q. Chen, and Z. Chen, “A novel image/video coding method based on compressed sensing theory,” In Proceedings of IEEE ICASSP, pp. 1361-1364, April 2008, proposed a method of image/video coding by employing transform coefficient subsampling and total variation (TV) minimization based post processing of preliminary block reconstruction in the residue domain.
M. R. Dadkhah, S. Shirani, M. J. Deen, “Compressive sensing with modified total variation minimization algorithm”, In Proceedings of IEEE ICASSP, pp. 1030-1033, Mar. 14-19, 2010, mention exploiting Norm-1 post-processing for image reconstruction.
Another example of the use of total variation-minimization-based post processing can be found in T. T. Do, X. Lu, J. Sole, “Compressive sensing with adaptive pixel domain reconstruction for block-based video coding”, In Proceedings of ICIP, pp. 3377-3380 Sep. 26-29, 2010. Therein, a video encoder is proposed which selects between a new coding mode using adaptive total variation minimization block recovery and existing H.264 modes. An additional flag, denoted as CS-flag, is employed to mark the selected coding mode. The decoder reads the CS-flag and then executes the appropriate reconstruction algorithm corresponding to the CS mode or the normal modes.